CSE 373: Data Structures and Algorithms

Winter 2000

Assignment 6 Chapter 7 Due February 25, 2000

 

Please include your name and student id # on what you turn in.

 

  1. Exercise 7.4 (7.4 in C++ book).  Show the intermediate results of Shell sort after running through each increment.  That is, use the 7 increment and show the intermediate results, then use the 3 increment and show the intermediate results.  You can skip showing the 1 increment because that’s should be a sorted list.

 

  1. Exercise 7.11 (7.11 in C++ book).  Be sure to show the intermediate results after each iteration, and only use half the input value from the problem 142, 543, 123, 65, 453, 879

 

  1. Exercise 7.17 (7.15 in C++ book).  Be sure to show the intermediate results after each iteration

 

  1. Fill in the average (i.e., expected) running times for the following sorting algorithms on the various ordered data

 

 

Insertion Sort

Bubble Sort

Shell Sort

 

Heap Sort

Merge Sort

Quick Sort

Sorted Input

 

 

O(N)

 

 

 

O(NlogN)

 

 

Reverse Sorted Input

 

 

O(N2)

 

 

 

O(NlogN)

 

Random Input

 

 

 

 

 

 

O(N3/2)

 

 

 

O(NlogN)